package l3;


public class LinkedList<T> implements List<T> {
    private Node<T> head;
    private int size;

    public static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    public LinkedList() {
        head = new Node<T>(null);
        size = 0;
    }

    public void clear() {
        head.next = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        Node<T> p = head.next;
        int count = 0;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }
    public int size1(){
        return size();
    }

    public void traverse() {
        Node<T> p = head.next;
        while (p != null) {
            System.out.println(p.data);
            p = p.next;
        }
        System.out.println();
    }

    public T visit(int index) {
        if (index < 0||index >= size) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        Node<T> p = head.next;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p.data;
    }

    public int search(T value) {
        Node<T> p = head.next;
        for (int i = 0; i < size; i++) {
            if (p.data.equals(value)) {
                return i;
            }
            p = p.next;
        }
        return -1;
    }

    public void insert(int index, T value) {
        if (index < 0||index > size) {
            throw  new IndexOutOfBoundsException("索引越界");
        }
        Node<T> newNode = new Node<>(value);
        Node<T> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        newNode.next = p.next;
        p.next = newNode;
        size++;
    }

    public void remove(int index) {
        if (index < 0||index >= size) {
            throw  new IndexOutOfBoundsException("索引越界");
        }
        Node<T> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        p.next = p.next.next;
        size--;
    }
}
